#include <bits/stdc++.h>
using namespace std;
const int maxa = 1e6+100;
int A[maxa];
int amin[maxa], amax[maxa];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, k; cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }

    //V1:deque
//    deque<int> qmin;
//    deque<int> qmax;
//    for (int p = 0; p < n; ++p) {
//        int a = A[p];
//        while(!qmin.empty() && qmin.back() > a) qmin.pop_back();
//        while(!qmax.empty() && qmax.back() < a) qmax.pop_back();
//        qmin.push_back(a);
//        qmax.push_back(a);
//        if(p-k>=0 && A[p-k] == qmin.front()) qmin.pop_front();
//        if(p-k>=0 && A[p-k] == qmax.front()) qmax.pop_front();
//        if(p >= k-1) qmin[p-k+1] = qmin.front();
//        if(p >= k-1) amax[p-k+1] = qmax.front();
//    }
//    for (int i = 0; i < n-k+1; ++i) {
//        if(i) cout << ' ' << qmin[i];
//        else cout << qmin[i];
//    }
//    cout << "\n";
//    for (int i = 0; i < n-k+1; ++i) {
//        if(i) cout << ' ' << amax[i];
//        else cout << amax[i];
//    }
    //V2:array:
    deque<int> qmin, qmax;
    for (int p = 0; p < n; ++p) {
        int a = A[p];
        while(!qmin.empty() && a <= A[qmin.back()]) qmin.pop_back();
        while(!qmax.empty() && a >= A[qmax.back()]) qmax.pop_back();
        qmin.push_back(p);
        qmax.push_back(p);
        if(qmin.front() < p-k+1) qmin.pop_front();
        if(qmax.front() < p-k+1) qmax.pop_front();
        amin[p] = A[qmin.front()];
        amax[p] = A[qmax.front()];
    }

    for (int i = k-1; i < n; ++i) {
        if(i == k-1) cout << amin[i];
        else cout << ' ' << amin[i] ;
    }
    cout << "\n";
    for (int i = k-1; i < n; ++i) {
        if(i == k-1) cout << amax[i];
        else cout << ' ' << amax[i] ;
    }
    return 0;
}